/*
* @(#) Sort.java 2018年02月06日
*
* Copyright 2010 NetEase.com, Inc. All rights reserved.
*/
package com.leo.m1802.d06;

import java.util.Arrays;

/**
 *
 * @author xuexiaolei
 * @version 2018年02月06日
 */
public class Sort {
    private void swap(int[] s, int i, int j){
        int temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    public void simpleInsert(int[] a){
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j>0 ; j--) {
                if (a[j] < a[j-1]) {
                    swap(a, j, j-1);
                }else {
                    break;
                }
            }
        }
    }

    public void bullelSort(int[] a){
        for (int i = a.length-1; i >=0 ; i--) {
            for (int j = 0; j < i; j++) {
                if (a[i] < a[j]){ swap(a, i, j); }
            }
        }
    }

    private int partition(int[] a, int start, int end){
        int temp = a[start];
        int i=start,j=end;
        while (i < j){
            while (i < j && a[j]>=temp){ j--; }
            a[i] = a[j];
            while (i < j && a[i]<=temp){i++;}
            a[j] = a[i];
        }
        a[i] = temp;
        return i;
    }

    private void quickSort(int[] a, int start, int end){
        if (start < end){
            int p = partition(a, start, end);
            quickSort(a, start, p-1);
            quickSort(a, p+1, end);
        }
    }

    public void quickSort(int[] a){
        quickSort(a, 0, a.length-1);
    }

    private void heapFix(int[] s, int i, int end){
        //计算可能需要替换的节点
        int replace = 2*i+1;
        if (replace > end) {return;}
        if (replace+1<=end && s[replace] < s[replace+1]){ replace++; }
        //调整
        if (s[i] < s[replace]){
            swap(s, i, replace);
            heapFix(s, replace, end);
        }
    }

    public void heapSort(int[] s){
        for (int i = (s.length/2); i>=0; i--) {
            heapFix(s, i, s.length-1);
        }
        for (int i = s.length-1; i >0 ; i--) {
            swap(s, i, 0);
            heapFix(s, 0, i-1);
        }
    }

    public static void main(String[] args) {
        Sort s = new Sort();
        int[] a = new int[]{5,1,5,67,3,53,234,52,42,13,452,35,6,0,-1,3};
//        s.simpleInsert(a);
//        s.bullelSort(a);
//        s.quickSort(a);
        s.heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}
